package com.aqie.easy.stack;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * 496. 没有重复元素的 两个数组 下一个更大元素 I
 */
public class NextGreaterElement {
    public static int[] nextGreaterElement(int[] nums1, int[] nums2) {
        // 1. map 将小数组存进去, map格式 [数组中数字 => 下一个更大元素 偏移量],题干不重复保证可以在map中对两个数组取出同一个值
        Map<Integer,Integer> map = new HashMap<>();
        for (int num: nums1){
            map.put(num,-1);
        }
        // 2. 单调栈找大数组下一个最大值
        int length = nums2.length;
        Stack<Integer> stack = new Stack<>();
        for(int i = 0; i < length; i++){
            while(!stack.empty() && nums2[stack.peek()] < nums2[i]){
                map.put(nums2[stack.peek()], i - stack.peek());
                stack.pop();
            }
            stack.push(i);
        }
        // 3. 根据上面map将 nums1数组赋值
        for (int i=0; i< nums1.length;i++){
            nums1[i] = map.get(nums1[i]);
        }
        // 4. 数组输出的是下一个最大值的偏移量(题干要输出下一个最大值)
        System.out.println(Arrays.toString(nums1));
        return nums1;
    }


    public static int[] nextGreaterElement2(int[] nums1, int[] nums2) {
        // 1. map 将小数组存进去, map格式 [数组中数字 => 下一个更大元素],题干不重复保证可以在map中对两个数组取出同一个值
        Map<Integer,Integer> map = new HashMap<>();
        for (int num: nums1){
            map.put(num,-1);
        }
        // 2. 单调栈找大数组下一个最大值, 栈中存储的是nums2中元素
        int length = nums2.length;
        Stack<Integer> stack = new Stack<>();
        for(int i = 0; i < length; i++){
            while(!stack.empty() && stack.peek() < nums2[i]){
                map.put(stack.peek(), nums2[i]);
                stack.pop();
            }
            stack.push(nums2[i]);
        }
        // 3. 根据上面map将 nums1数组赋值
        for (int i=0; i< nums1.length;i++){
            nums1[i] = map.get(nums1[i]);
        }
        System.out.println(Arrays.toString(nums1));
        return nums1;
    }

    public static int[] nextLarger(int[] nums){
        int length = nums.length;
        int[] output = new int[length];
        for (int i = 0; i < length; i++){
            output[i] = -1;
        }

        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < length; i++){
            /**
             * 栈 保存的数组下标
             * 栈顶元素如果比数组元素小
             */
            while (!stack.empty() && nums[stack.peek()] < nums[i]){
                output[stack.peek()] = i - stack.peek();
                stack.pop();
            }
            stack.push(i);
        }
        return output;
    }

    public static void main(String[] args) {
        /*int[] arr = {1,3,1,2,4};
        int[] output = nextLarger(arr);
        System.out.println(Arrays.toString(output)); */           // [1, 3, 1, 1, 0]
        int[] nums1 = {4,1,2};
        int[] nums2 = {1,3,4,2};
        // int[] output = nextGreaterElement(nums1, nums2);        //  [-1, 1, -1]
        int[] output2 = nextGreaterElement2(nums1, nums2);       //


    }
}
